/*
 * @lc app=leetcode id=76 lang=cpp
 *
 * [76] Minimum Window Substring
 */
class Solution {
public:
    string minWindow(string s, string t) {
        int slen = s.size();
        int tlen = t.size();
        string ret = "";
        if (slen < tlen) {
            return ret;
        }

        int t_wc = 0;
        unordered_map<char, int> tmap, smap;
        for (auto c : t)  {
            tmap[c]++;
        }
        t_wc = tmap.size();

        int l = 0, r = 0;
        int minLen = INT_MAX;
        int idx = 0;
        int len = 0;
        int wc = 0;
        while (r < slen) {
            auto c = s[r];
            if (tmap.find(c) != tmap.end()) {
                smap[c]++;
                if (smap[c] == tmap[c]) {
                    wc++;
                }

                while (l <= r && wc == t_wc) {

                    len = r-l+1;
                    if (len < minLen) {
                        minLen = len;
                        idx = l;
                    }

                    auto c = s[l];
                    if (tmap.find(c) != tmap.end()) {
                        smap[c]--;
                        if (smap[c] < tmap[c]) {
                            wc--;
                        }
                    }
                    l++;
                }
            }
            r++;
        }

        if (minLen <= slen && minLen >= tlen) {
            ret = s.substr(idx, minLen);
        }

        return ret;
    }

};

